Generally, an error correction apparatus is applied to a digital communication system or a digital storage system, and can correct errors generated in the data to be received or to be reproduced.
As an example of the conventional error correction technique, there is a Japanese patent laid-open publication No. sho 57-25047 entitled "Error Correction Method" by SONY Corporation of Japan, published on Feb. 9, 1982. This publication discloses a method which can correct even two-word errors in a block of data having n words, each of which is composed of m bits.
The detailed descriptions are as follows.
The K syndromes S.sub.0 to S.sub.K-1 are obtained from a block of data V.sup.T consisting of n words to be received and a parity check matrix H by the following operation: ##EQU1##
Here, the parity check matrix H has n columns and k rows, and each of the elements in a predetermined row is selected among .alpha..sup.0 (=1) to .alpha..sup.2m-2, where the element .alpha. is a root value satisfying the equation F(X)=0. Thus, two identical values are not found within the predetermined row, and the elements in the other rows are selected by the involution of the corresponding elements of the predetermined row. The parity check matrix H is represented as follows: ##EQU2##
In case of a double word error ei and ej, the equations for the syndromes S.sub.0, S.sub.1, S.sub.2, S.sub.3 are as follows: EQU S.sub.0 =ei+ej EQU S.sub.1 =.alpha..sup.i ei+.alpha..sup.j ej EQU S.sub.2 =.alpha..sup.2i ei+.alpha..sup.2j ej EQU S.sub.3 =.alpha..sup.3i ei+.alpha..sup.3j ej.
The above equations can be modified as follows: EQU (.alpha..sup.i S.sub.0 +S.sub.1)(.alpha..sup.i S.sub.2 +S.sub.3)=(.alpha..sup.i S.sub.1 +S.sub.2).sup.2.
If the equation is again modified, the following error location polynomial is obtained: EQU (S.sub.0 S.sub.2 +S.sub.1.sup.2).alpha..sup.2i +(S.sub.1 S.sub.2 +S.sub.0 S.sub.3).alpha..sup.i +(S.sub.1 S.sub.3 +S.sub.2.sup.2)=0 EQU S.sub.0 S.sub.2 +S.sub.1.sup.2 =A EQU S.sub.1 S.sub.2 +S.sub.0 S.sub.3 =B EQU S.sub.1 S.sub.3 +S.sub.2.sup.2 =C
The error locations for two-word errors can be calculated by using the coefficients A, B, and C of the polynomial equation.
[1] In the case of no errors: EQU A=B=C=0, S.sub.0 =0, S.sub.3 =0.
[2] In the case of a one-word error:
When A=B=C=0, S.sub.0 .noteq.0, and S.sub.3 .noteq.0, a one-word error is determined. An error location i can be easily obtained from the equation .alpha..sup.i =S.sub.1 /S.sub.0, and an error correction can be made using ei=S.sub.0.
[3] In the case of a two-word error:
In the case of an error of two words or more, the relationships of A.noteq.0, B.noteq.0 and C.noteq.0 are satisfied. At this time, the following relationship is satisfied: EQU A.alpha..sup.2i +B.alpha..sup.1 +C=0
in which i ranges from zero to n-1.
If it is assumed that the relationships of B/A=D and C/A=E are satisfied, the following equations are obtained: EQU D=.alpha..sup.i +.alpha..sup.j EQU E=.alpha..sup.i .alpha..sup.j.
Accordingly, the following equation is derived from the above equations: EQU .alpha..sup.2i +D.alpha..sup.i +E=0.
Here, when the difference of two error locations is t, that is, when the relationship of j=i+t is satisfied, the following equations are obtained: EQU D=.alpha..sup.i (1+.alpha..sup.t) EQU E=.alpha..sup.2i+t.
Whereby, the following equation can be further derived: ##EQU3##
The values of .alpha..sup.-t +.alpha..sup.t for t=1 to (n-1) are previously stored in ROM, and t is obtained by detecting an agreement between an output of ROM and a value of D.sup.2 /E calculated from the received word. If there is no agreement, the error is determined to be three words or more.
Thus, the following relationships are assumed: ##EQU4## Through derivation, the following equations are true: ##EQU5##
From the above equations, the error locations i and j are obtained. Then, the error patterns ei and ej are represented as follows: ##EQU6## The error locations and error patterns are obtained through the above-mentioned process, so that the error of the received word at the corresponding error locations can be corrected according to the error patterns.
However, in the method proposed in the Japanese patent laid-open publication No. Sho 57-25047, in order to obtain the error locations, the error locator polynomial .alpha..sup.2i +D .alpha..sup.i +E=0 is solved to obtain two roots .alpha..sup.i, .alpha..sup.j from which the error locations i and j are obtained, making the circuit required for the operations overly complicated, and the operational delay time overly long.